package Leetcode;

import java.util.Arrays;

/**
 * 给你一个整数数组 nums ，找出 nums 的下一个排列。
 * 必须 原地 修改，只允许使用额外常数空间。
 * 输入：nums = [1,2,3]
 * 输出：[1,3,2]
 * 输入：nums = [3,2,1]
 * 输出：[1,2,3]
 * 输入：nums = [1,1,5]
 * 输出：[1,5,1]
 * 输入：nums = [1,3,2]
 * 输出：[1,5,1]
 */
public class 力扣31_下一个排列 {
    public static void main(String[] args) {
        int[] nums1 = {1, 2, 3};
        int[] nums2 = {3, 2, 1};
        int[] nums3 = {1, 1, 5};
        int[] nums4 = {1, 3, 2};
        int[] nums5 = {3, 2, 1};
        int[] nums6 = {5, 4, 7, 5, 3, 2};
        int[] nums7 = {4, 2, 0, 2, 3, 2, 0};
        nextPermutation(nums1);
        nextPermutation(nums2);
        nextPermutation(nums3);
        nextPermutation(nums4);
        nextPermutation(nums5);
        nextPermutation(nums6);
        nextPermutation(nums7);
        System.out.println(Arrays.toString(nums1));
        System.out.println(Arrays.toString(nums2));
        System.out.println(Arrays.toString(nums3));
        System.out.println(Arrays.toString(nums4));
        System.out.println(Arrays.toString(nums5));
        System.out.println(Arrays.toString(nums6));
        System.out.println(Arrays.toString(nums7));
    }

    /**
     * 注意到下一个排列总是比当前排列要大，除非该排列已经是最大的排列。我们希望找到一种方法，能够找到一个大于当前序列的新序列，且变大的幅度尽可能小。具体地：
     * 我们需要将一个左边的「较小数」与一个右边的「较大数」交换，以能够让当前排列变大，从而得到下一个排列。
     * 同时我们要让这个「较小数」尽量靠右，而「较大数」尽可能小。当交换完成后，「较大数」右边的数需要按照升序重新排列。
     * 这样可以在保证新排列大于原来排列的情况下，使变大的幅度尽可能小。
     */
    static void nextPermutation(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        int i = nums.length - 2;
        // 寻找较小数 从后往前找第一个趋势减小的数字   比如 1 2 6 5 4 3 找到2
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        // 寻找较大数 在
        if (i >= 0) {
            int j = nums.length - 1;
            while (j > 0 && nums[i] >= nums[j]) {
                j--;
            }
            // 交换 使其增长
            swap(nums, i, j);
        }
        // 反转 使其增长幅度尽可能小
        reverse(nums, i + 1);
    }

    static void swap(int[] nums, int a, int b) {
        int num = nums[a];
        nums[a] = nums[b];
        nums[b] = num;
    }

    static void reverse(int[] nums, int l) {
        int r = nums.length - 1;
        while (l < r) {
            swap(nums, l++, r--);
        }
    }

}
